package 滑动窗口And双指针.双指针;

import org.junit.Test;

import java.util.*;

/**
 * @author aodre , QQ : 480029069
 * @date 2023/7/9 20:07
 */
public class lc15三数之和 {


    /*
        这样写的话,好像没办法 去重
     */

    private int sum;
    public void  dfs(int index, int k, List<List<Integer>> ans, Deque<Integer> path,int nums[],boolean used[]){
        if(k == 0 && sum == 0){
            ans.add(new ArrayList<>(path));
            return ;
        }
        if(index == nums.length || k ==0 ){
            return ;
        }


        // 两个决策 选 和不选
        // no
        dfs(index + 1,k,ans,path,nums,used);

        if(index > 0 &&  nums[index] == nums[index - 1] && !used[index - 1]){ // 去重
            return ;
        }
        // yes
        sum += nums[index];
        path.addLast(nums[index]);
        used[index] = true;
        dfs(index + 1,k - 1,ans,path,nums,used);
        used[index] = false;
        sum -= nums[index];
        path.removeLast();
    }

    public List<List<Integer>> solve(int nums[]){
        List<List<Integer>> ans = new ArrayList<>();
        Deque<Integer> path = new ArrayDeque<>();
        Arrays.sort(nums); // 排个序, 便于去重
        boolean used[] = new boolean[nums.length];
        dfs(0,3,ans,path,nums,used);
        return ans;
    }

    @Test
    public void test(){
        int nums[] = {-2,0,1,1,2};
        System.out.println(solve(nums));
        System.out.println(solution(nums));
    }


    public void  dfs(int index, int k, int sum,List<List<Integer>> ans, Deque<Integer> path,int nums[]){
        if(k == 0 && sum == 0){
            ans.add(new ArrayList<>(path));
            return ;
        }
        if(k == 0){  // 这还能剪个枝
            return ;
        }
        for(int i = index;i < nums.length && k - path.size() <= nums.length - i + 1;i++){
            if(i > index && nums[i] == nums[i - 1]){ //
                continue;
            }
            path.addLast(nums[i]);
            dfs(i + 1,k - 1,sum + nums[i],ans,path,nums);
            path.removeLast();
        }
    }




    // 双指针
    /*
     固定枚举 k 在 l ~ r 进行双指针
     可以  不用 set 进行 去重
     直接
     i > 0 && nums[k] == nums[k - 1]  continue;
     */
    public List<List<Integer>> solution(int nums[]){
        List<List<Integer>> ans = new ArrayList<>();
        Arrays.sort(nums);
        Set<Integer> set = new HashSet<>(); // 对 k 进行去重, 这里非常的巧妙!
        for(int k = 0; k < nums.length - 2;k++ ){
            if(nums[k] > 0){
                break;
            }
            if(set.contains(nums[k])){
                continue;
            }
            set.add(nums[k]);
            int l = k + 1, r = nums.length - 1 , val = -nums[k];
            while(l < r){
                if(nums[l] + nums[r] == val){
                   ans.add(Arrays.asList(nums[k],nums[l],nums[r]));
                   // 对 l ~ r 进行去重
                    while(nums[r - 1] == nums[r] && r > l){
                        r--;
                    }
                    while(nums[l] == nums[l + 1] && l < r){
                        l++;
                    }
                    l++;
                    r--;

                }else if(nums[l] + nums[r] < val){
                    l++;
                }else{
                    r--;
                }
            }
        }
        return ans;
    }


}

/*
  这到底在做一件什么事情, 为什么这么快?   0ms
  重写了 List
 */
class Solution {

    private List<List<Integer>>result;
    public List<List<Integer>> threeSum(int[] nums) {
        return new AbstractList<List<Integer>>() {
            @Override
            public List<Integer> get(int index) {
                init();
                return result.get(index);
            }

            private void init() {
                if(result!=null) return;
                result= new ArrayList<>();
                int n=nums.length;
                Arrays.sort(nums);
                for(int i=0;i<n-2;i++){
                    if(nums[i]>0){
                        break;
                    }
                    if (i>0 && nums[i] == nums[i-1]) continue;
                    int j=i+1;
                    int k=n-1;
                    while(j < k){
                        int x=nums[i]+nums[j]+nums[k];
                        if(x==0){
                            result.add(Arrays.asList(nums[i], nums[j], nums[k]));
                            while(j<k&&nums[j]==nums[j+1]) j++;
                            while(j<k&&nums[k]==nums[k-1]) k--;
                            j++;
                            k--;
                        }
                        else if(x>0){
                            while(j<k&&nums[k]==nums[k-1]) k--;
                            k--;
                        }
                        else{
                            while(j<k&&nums[j]==nums[j+1]) j++;
                            j++;
                        }
                    }
                }

            }

            @Override
            public int size() {
                init();
                return result.size();
            }
        };
    }
}